package offer.day13;

public class No18First_deleteNode {
    /*
     * 面试题18：删除链表的节点
     * 题目一：在O(1)时间内删除链表节点
     *给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点与函数的定义如下：
     *struct ListNode{
     *	int m_nValue;
     *	ListNode* m_pNext;
     *};
     *
     *void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);
     *
     *思路:删除链表节点有三种情况：
     *1、只有一个节点，删除头节点即是尾节点，直接head.next = null即可
     *2、删除的节点不是尾节点，找到要删除的下一个节点将其数据赋值给要删除的节点，并且将下一个节点的next赋值给要删除的节点的next即可
     *3、删除的节点是尾节点，但是前面有很多个节点，则需要从头节点遍历到要删除的前一个节点，然后将这个节点的next置空null即可。
     * */

    //定义ListNode节点  静态


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        ListNode six = new ListNode(6);
        ListNode seven = new ListNode(7);
        head.next = second;
        second.next = three;
        three.next = four;
        four.next = five;
        five.next = six;
        six.next = seven;
        seven.next = null;
        showNode(head);
        deleteNode(head,four);
        showNode(head);
    }

    public static void showNode(ListNode head){
        ListNode tmp=head;
        while(tmp!=null){
            System.out.println(tmp);
            tmp=tmp.next;
        }
        System.out.println();
    }

    public static void deleteNode(ListNode head,ListNode deleteNode){
        if(head==null || deleteNode==null){
            return;
        }
        if(head==deleteNode){
            head.next=null;
            return ;
        }
        ListNode tmp=head;
        while(tmp.next!=deleteNode){
            tmp=tmp.next;
        }
        tmp.next=deleteNode.next;
    }
}

